package main

import (
	"fmt"
)

/**
执行用时：208 ms, 在所有 Go 提交中击败了68.76%的用户
内存消耗：9.6 MB, 在所有 Go 提交中击败了48.52%的用户
 */
func maxSlidingWindow(nums []int, k int) []int {

	n := len(nums)
	q := make([]int, n)
	hh, tt := 0, -1
	res := []int{}
	for i := 0; i < n; i++ {
		if hh <= tt && i - k + 1 > q[hh] { hh++ }
		for hh <= tt && nums[q[tt]] < nums[i] { tt-- }
		q[tt + 1] = i
		tt++
		if i >= k - 1 { res = append(res, nums[q[hh]]) }
	}
	return res
}

func main() {

	nums := []int{1, 3, -1, -3, 5, 3, 6, 7}
	fmt.Println(maxSlidingWindow(nums, 3))
}
